<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, minimum-scale=1, user-scalable=no, minimal-ui">
  <meta name="renderer" content="webkit">
  <meta http-equiv="Cache-Control" content="no-transform" />
  <meta http-equiv="Cache-Control" content="no-siteapp" />
  <meta name="apple-mobile-web-app-capable" content="yes">
  <meta name="apple-mobile-web-app-status-bar-style" content="black">
  <meta name="format-detection" content="telephone=no,email=no,adress=no">
  <!-- Color theme for statusbar -->
  <meta name="theme-color" content="#000000" />
  <!-- 强制页面在当前窗口以独立页面显示,防止别人在框架里调用页面 -->
  <meta http-equiv="window-target" content="_top" />
  
  
  <title>二叉树 | 金旭的个人博客</title>
  <meta name="description" content="一棵二叉树是节点的一个有限集合，该集合后者为空，或者有一个根节点加上两课左子树和右子树组成。 二叉树的特点 每个节点最多有两棵子树，每个节点的度不大于2 二叉树的子书有左右之分二叉树的性质&#x2F;&#x2F; int_Down, int_Up分别表示向下和向上取整 在二叉树的第i（i&gt;&#x3D;1）层最多有2^(i-1)个节点 深度为k（k&gt;&#x3D;0）的二叉树最少有k个节点，最多有2^k-1个节点 对于任一棵非空">
<meta property="og:type" content="article">
<meta property="og:title" content="二叉树">
<meta property="og:url" content="http://sunjinxu99.gitee.io/blog/2020/03/26/%E6%A0%91/index.html">
<meta property="og:site_name" content="金旭的个人博客">
<meta property="og:description" content="一棵二叉树是节点的一个有限集合，该集合后者为空，或者有一个根节点加上两课左子树和右子树组成。 二叉树的特点 每个节点最多有两棵子树，每个节点的度不大于2 二叉树的子书有左右之分二叉树的性质&#x2F;&#x2F; int_Down, int_Up分别表示向下和向上取整 在二叉树的第i（i&gt;&#x3D;1）层最多有2^(i-1)个节点 深度为k（k&gt;&#x3D;0）的二叉树最少有k个节点，最多有2^k-1个节点 对于任一棵非空">
<meta property="og:image" content="https://gitee.com/sunjinxu99/image/raw/master/img/20200403163308.png">
<meta property="og:image" content="https://gitee.com/sunjinxu99/image/raw/master/img/20200403163457.png">
<meta property="article:published_time" content="2020-03-26T06:55:13.716Z">
<meta property="article:modified_time" content="2021-07-07T13:14:39.076Z">
<meta property="article:author" content="金旭">
<meta property="article:tag" content="数据结构">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gitee.com/sunjinxu99/image/raw/master/img/20200403163308.png">
  <!-- Canonical links -->
  <link rel="canonical" href="http://sunjinxu99.gitee.io/blog/2020/03/26/%E6%A0%91/index.html">
  
    <link rel="alternate" href="/atom.xml" title="金旭的个人博客" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png" type="image/x-icon">
  
  
<link rel="stylesheet" href="/blog/css/style.css">

  
  
  
  
<meta name="generator" content="Hexo 4.2.0"></head>


<body class="main-center theme-blue# 主题颜色 theme-black theme-blue theme-green theme-purple" itemscope itemtype="http://schema.org/WebPage">
  <header class="header" itemscope itemtype="http://schema.org/WPHeader">
  <div class="slimContent">
    <div class="navbar-header">
      
      
      <div class="profile-block text-center">
        <a id="avatar" href="" target="_blank">
          <img class="img-circle img-rotate" src="/blog/images/avatar.png" width="200" height="200">
        </a>
        <h2 id="name" class="hidden-xs hidden-sm">小马</h2>
        <h3 id="title" class="hidden-xs hidden-sm hidden-md"></h3>
        <small id="location" class="text-muted hidden-xs hidden-sm"><i class="icon icon-map-marker"></i> </small>
      </div>
      
      <div class="search" id="search-form-wrap">

    <form class="search-form sidebar-form">
        <div class="input-group">
            <input type="text" class="search-form-input form-control" placeholder="Search" />
            <span class="input-group-btn">
                <button type="submit" class="search-form-submit btn btn-flat" onclick="return false;"><i class="icon icon-search"></i></button>
            </span>
        </div>
    </form>
    <div class="ins-search">
  <div class="ins-search-mask"></div>
  <div class="ins-search-container">
    <div class="ins-input-wrapper">
      <input type="text" class="ins-search-input" placeholder="Type something..." x-webkit-speech />
      <button type="button" class="close ins-close ins-selectable" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button>
    </div>
    <div class="ins-section-wrapper">
      <div class="ins-section-container"></div>
    </div>
  </div>
</div>


</div>
      <button class="navbar-toggle collapsed" type="button" data-toggle="collapse" data-target="#main-navbar" aria-controls="main-navbar" aria-expanded="false">
        <span class="sr-only">Toggle navigation</span>
        <span class="icon-bar"></span>
        <span class="icon-bar"></span>
        <span class="icon-bar"></span>
      </button>
    </div>
    <nav id="main-navbar" class="collapse navbar-collapse" itemscope itemtype="http://schema.org/SiteNavigationElement" role="navigation">
      <ul class="nav navbar-nav main-nav ">
        
        
        <li class="menu-item menu-item-home">
          <a href="/blog/.">
            
            <i class="icon icon-home-fill"></i>
            
            <span class="menu-title">Home</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-archives">
          <a href="/blog/archives">
            
            <i class="icon icon-archives-fill"></i>
            
            <span class="menu-title">Archives</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-categories">
          <a href="/blog/categories">
            
            <i class="icon icon-folder"></i>
            
            <span class="menu-title">Categories</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-tags">
          <a href="/blog/tags">
            
            <i class="icon icon-tags"></i>
            
            <span class="menu-title">Tags</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-about">
          <a href="/blog/about">
            
            <i class="icon icon-cup-fill"></i>
            
            <span class="menu-title">About</span>
          </a>
        </li>
        
      </ul>
      
    </nav>
  </div>
</header>

  
    <aside class="sidebar" itemscope itemtype="http://schema.org/WPSideBar">
  <div class="slimContent">
    
      <div class="widget">
    <h3 class="widget-title">Board</h3>
    <div class="widget-body">
        <div id="board">
            <div class="content">
                <p>朝闻道夕死可矣</p>
            </div>
        </div>
    </div>
</div>

    
      
  <div class="widget">
    <h3 class="widget-title">Categories</h3>
    <div class="widget-body">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/blog/categories/JavaSE/">JavaSE</a><span class="category-list-count">7</span></li><li class="category-list-item"><a class="category-list-link" href="/blog/categories/LeetCode/">LeetCode</a><span class="category-list-count">3</span><ul class="category-list-child"><li class="category-list-item"><a class="category-list-link" href="/blog/categories/LeetCode/%E7%AE%97%E6%B3%95/">算法</a><span class="category-list-count">3</span></li></ul></li><li class="category-list-item"><a class="category-list-link" href="/blog/categories/%E6%9D%82%E8%AE%B0/">杂记</a><span class="category-list-count">1</span></li></ul>
    </div>
  </div>


    
      
  <div class="widget">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget-body tagcloud">
      <a href="/blog/tags/IO%E6%B5%81/" style="font-size: 13px;">IO流</a> <a href="/blog/tags/OSI%E5%8F%82%E8%80%83%E6%A8%A1%E5%9E%8B/" style="font-size: 13px;">OSI参考模型</a> <a href="/blog/tags/TCP-IP%E5%8F%82%E8%80%83%E6%A8%A1%E5%9E%8B/" style="font-size: 13px;">TCP/IP参考模型</a> <a href="/blog/tags/ftp%E5%8D%8F%E8%AE%AE/" style="font-size: 13px;">ftp协议</a> <a href="/blog/tags/http/" style="font-size: 13px;">http</a> <a href="/blog/tags/leetcode/" style="font-size: 13px;">leetcode</a> <a href="/blog/tags/%E4%BA%8C%E5%88%86%E6%95%B0%E7%BB%84/" style="font-size: 13px;">二分数组</a> <a href="/blog/tags/%E4%BA%8C%E5%8F%89%E6%A0%91/" style="font-size: 13px;">二叉树</a> <a href="/blog/tags/%E5%85%A8%E6%8E%92%E5%88%97/" style="font-size: 13px;">全排列</a> <a href="/blog/tags/%E5%8F%8C%E6%8C%87%E9%92%88/" style="font-size: 13.33px;">双指针</a> <a href="/blog/tags/%E5%8F%8D%E5%B0%84/" style="font-size: 13px;">反射</a> <a href="/blog/tags/%E5%93%88%E5%B8%8C%E8%A1%A8/" style="font-size: 13.67px;">哈希表</a> <a href="/blog/tags/%E5%9B%9E%E6%BA%AF%E6%B3%95/" style="font-size: 13px;">回溯法</a> <a href="/blog/tags/%E5%A4%9A%E7%BA%BF%E7%A8%8B/" style="font-size: 13px;">多线程</a> <a href="/blog/tags/%E5%AD%97%E7%AC%A6%E4%B8%B2/" style="font-size: 13px;">字符串</a> <a href="/blog/tags/%E6%8E%92%E5%BA%8F/" style="font-size: 13.33px;">排序</a> <a href="/blog/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" style="font-size: 14px;">数据结构</a> <a href="/blog/tags/%E6%9D%82%E8%AE%B0/" style="font-size: 13px;">杂记</a> <a href="/blog/tags/%E6%A0%88/" style="font-size: 13px;">栈</a> <a href="/blog/tags/%E6%B3%9B%E5%9E%8B/" style="font-size: 13px;">泛型</a> <a href="/blog/tags/%E7%AE%97%E6%B3%95/" style="font-size: 13.33px;">算法</a> <a href="/blog/tags/%E8%8F%B2%E6%B3%A2%E9%82%A3%E5%88%87%E6%95%B0%E5%88%97/" style="font-size: 13.33px;">菲波那切数列</a> <a href="/blog/tags/%E9%80%92%E5%BD%92/" style="font-size: 13px;">递归</a> <a href="/blog/tags/%E9%93%BE%E8%A1%A8/" style="font-size: 13.33px;">链表</a> <a href="/blog/tags/%E9%98%9F%E5%88%97/" style="font-size: 13px;">队列</a> <a href="/blog/tags/%E9%9D%A2%E5%90%91%E5%AF%B9%E8%B1%A1/" style="font-size: 13px;">面向对象</a>
    </div>
  </div>

    
      
  <div class="widget">
    <h3 class="widget-title">Archive</h3>
    <div class="widget-body">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2021/07/">July 2021</a><span class="archive-list-count">9</span></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2020/07/">July 2020</a><span class="archive-list-count">3</span></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2020/05/">May 2020</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2020/04/">April 2020</a><span class="archive-list-count">8</span></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2020/03/">March 2020</a><span class="archive-list-count">10</span></li></ul>
    </div>
  </div>


    
      
  <div class="widget">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget-body">
      <ul class="recent-post-list list-unstyled no-thumbnail">
        
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                
              </p>
              <p class="item-title">
                <a href="/blog/2021/07/14/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%95%9C%E5%83%8F/" class="title">二叉树的镜像</a>
              </p>
              <p class="item-date">
                <time datetime="2021-07-14T12:34:40.165Z" itemprop="datePublished">2021-07-14</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                
              </p>
              <p class="item-title">
                <a href="/blog/2021/07/14/%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%8E%92%E5%BA%8F%E7%9A%84%E9%93%BE%E8%A1%A8/" class="title">合并两个排序的链表</a>
              </p>
              <p class="item-date">
                <time datetime="2021-07-14T09:26:07.612Z" itemprop="datePublished">2021-07-14</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                
              </p>
              <p class="item-title">
                <a href="/blog/2021/07/14/%E4%BB%8E%E5%B0%BE%E5%88%B0%E5%A4%B4%E6%89%93%E5%8D%B0%E9%93%BE%E8%A1%A8/" class="title">从尾到头打印链表</a>
              </p>
              <p class="item-date">
                <time datetime="2021-07-14T08:02:42.111Z" itemprop="datePublished">2021-07-14</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                
              </p>
              <p class="item-title">
                <a href="/blog/2021/07/14/%E6%9B%BF%E6%8D%A2%E7%A9%BA%E6%A0%BC/" class="title">替换空格</a>
              </p>
              <p class="item-date">
                <time datetime="2021-07-14T06:28:22.026Z" itemprop="datePublished">2021-07-14</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                
              </p>
              <p class="item-title">
                <a href="/blog/2021/07/14/%E6%97%8B%E8%BD%AC%E6%95%B0%E7%BB%84%E7%9A%84%E6%9C%80%E5%B0%8F%E6%95%B0%E5%AD%97/" class="title">旋转数组的最小数字</a>
              </p>
              <p class="item-date">
                <time datetime="2021-07-14T06:12:09.184Z" itemprop="datePublished">2021-07-14</time>
              </p>
            </div>
          </li>
          
      </ul>
    </div>
  </div>
  

    
  </div>
</aside>

  
  
<main class="main" role="main">
  <div class="content">
  <article id="post-树" class="article article-type-post" itemscope itemtype="http://schema.org/BlogPosting">
    
    <div class="article-header">
      
        
  
    <h1 class="article-title" itemprop="name">
      二叉树
    </h1>
  

      
      <div class="article-meta">
        <span class="article-date">
    <i class="icon icon-calendar-check"></i>
	<a href="/blog/2020/03/26/%E6%A0%91/" class="article-date">
	  <time datetime="2020-03-26T06:55:13.716Z" itemprop="datePublished">2020-03-26</time>
	</a>
</span>
        
        
  <span class="article-tag">
    <i class="icon icon-tags"></i>
	<a class="article-tag-link" href="/blog/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" rel="tag">数据结构</a>
  </span>


        

        <span class="post-comment"><i class="icon icon-comment"></i> <a href="/blog/2020/03/26/%E6%A0%91/#comments" class="article-comment-link">Comments</a></span>
        
      </div>
    </div>
    <div class="article-entry marked-body" itemprop="articleBody">
      
        <p>一棵二叉树是节点的一个有限集合，该集合后者为空，或者有一个根节点加上两课左子树和右子树组成。</p>
<h3 id="二叉树的特点"><a href="#二叉树的特点" class="headerlink" title="二叉树的特点"></a>二叉树的特点</h3><ol>
<li>每个节点最多有两棵子树，每个节点的度不大于2</li>
<li>二叉树的子书有左右之分<h3 id="二叉树的性质"><a href="#二叉树的性质" class="headerlink" title="二叉树的性质"></a>二叉树的性质</h3>// int_Down, int_Up分别表示向下和向上取整</li>
<li>在二叉树的第i（i&gt;=1）层最多有2^(i-1)个节点</li>
<li>深度为k（k&gt;=0）的二叉树最少有k个节点，最多有2^k-1个节点</li>
<li>对于任一棵非空二叉树，若其叶节点数为n0，度为2的非叶节点数为n2，则n0 = n2 + 1</li>
<li>具有n个节点的完全二叉树的深度为int_up(log(2,n+1))</li>
<li>如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号１，２，３，……，ｎ，然后按此结点编号将树中各结点顺序的存放于一个一维数组，并简称编号为i的结点为结点i（ ｉ&gt;=１ &amp;&amp; ｉ&lt;=ｎ）,则有以下关系:<ol>
<li>若 ｉ= 1，则结点i为根，无父结点；若 ｉ&gt; 1，则结点 i 的父结点为结点int_DOWN（ｉ / ２）; </li>
<li>若 ２＊ｉ &lt;= ｎ，则结点 ｉ 的左子女为结点 ２＊ｉ；</li>
<li>若２＊ｉ＜＝ｎ，则结点ｉ的右子女为结点２＊ｉ＋１；</li>
<li>若结点编号ｉ为奇数，且ｉ！＝１，它处于右兄弟位置，则它的左兄弟为结点ｉ－１； </li>
<li>若结点编号ｉ为偶数，且ｉ！＝ｎ，它处于左兄弟位置，则它的右兄弟为结点ｉ＋１； </li>
<li>结点ｉ所在的层次为 int_DOWN（log（2，ｉ））＋１。</li>
</ol>
</li>
</ol>
<h3 id="满二叉树"><a href="#满二叉树" class="headerlink" title="满二叉树"></a>满二叉树</h3><p>如果二叉树中除了叶子结点，每个节点的度都为2，则次二叉树称为满二叉树。<br><img src="https://gitee.com/sunjinxu99/image/raw/master/img/20200403163308.png" alt=""></p>
<h3 id="完全二叉树"><a href="#完全二叉树" class="headerlink" title="完全二叉树"></a>完全二叉树</h3><p>如果二叉树出去最后一层节点为二叉树，且最后一层的结点一次从左至右分布，则此二叉树被称为完全二叉树<br><img src="https://gitee.com/sunjinxu99/image/raw/master/img/20200403163457.png" alt=""></p>
<h3 id="二叉树的实现"><a href="#二叉树的实现" class="headerlink" title="二叉树的实现"></a>二叉树的实现</h3><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">BinaryTree</span><span class="params">(object)</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span><span class="params">(self,roootObj)</span>:</span></span><br><span class="line">        self.key = rootObj</span><br><span class="line">        self.leftChild = <span class="literal">None</span></span><br><span class="line">        self.rightChild = <span class="literal">None</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">insertLeft</span><span class="params">(self,newNode)</span>:</span></span><br><span class="line">        <span class="keyword">if</span> self.leftChild == <span class="literal">None</span>:</span><br><span class="line">            self.leftChild = BinaryTree(newNode)</span><br><span class="line">        <span class="keyword">else</span>:</span><br><span class="line">            t = BinaryTree(NewNode)</span><br><span class="line">            t.leftChild = self.leftChild</span><br><span class="line">            self.leftChild = t</span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">insertRight</span><span class="params">(self,newNode)</span>:</span></span><br><span class="line">        <span class="keyword">if</span> self.RightChild == <span class="literal">None</span>:</span><br><span class="line">            self.RightChild = BinaryTree(newNode)</span><br><span class="line">        <span class="keyword">else</span>:</span><br><span class="line">            t = BinaryTree(NewNode)</span><br><span class="line">            t.RightChild = self.RightChild</span><br><span class="line">            self.RightChild = t</span><br><span class="line">        <span class="function"><span class="keyword">def</span> <span class="title">getRightChild</span><span class="params">(self)</span>:</span></span><br><span class="line">            <span class="keyword">return</span> self.RightChild  </span><br><span class="line">        <span class="function"><span class="keyword">def</span> <span class="title">getleftChild</span><span class="params">(self)</span>:</span></span><br><span class="line">            <span class="keyword">return</span> self.leftChild  </span><br><span class="line">        <span class="function"><span class="keyword">def</span> <span class="title">setRootVal</span><span class="params">(self,obj)</span>:</span></span><br><span class="line">            self.key = obj</span><br><span class="line">        <span class="function"><span class="keyword">def</span> <span class="title">getRootVal</span><span class="params">(self)</span>:</span></span><br><span class="line">            <span class="keyword">return</span> self.key</span><br></pre></td></tr></table></figure>
<h3 id="二叉树的遍历"><a href="#二叉树的遍历" class="headerlink" title="二叉树的遍历"></a>二叉树的遍历</h3><p>以下为二叉树的前序遍历、中序遍历、后序遍历的递归和非递归实现</p>
<ul>
<li>递归版本<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">preOrder</span><span class="params">(self,root)</span>:</span></span><br><span class="line">    <span class="keyword">if</span> root:</span><br><span class="line">        print(root.val)</span><br><span class="line">        preOrder(root.left)</span><br><span class="line">        preOrder(root.right)</span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">inOrder</span><span class="params">(self,root)</span>:</span></span><br><span class="line">    <span class="keyword">if</span> root:</span><br><span class="line">        preOrder(root.left)</span><br><span class="line">        print(root.val)</span><br><span class="line">        preOrder(root.right)</span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">postOrder</span><span class="params">(self,root)</span>:</span></span><br><span class="line">    <span class="keyword">if</span> root:</span><br><span class="line">        preOrder(root.left)</span><br><span class="line">        preOrder(root.right)</span><br><span class="line">        print(root.val</span><br></pre></td></tr></table></figure></li>
<li>非递归版本<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">preOrder</span><span class="params">(self, root)</span>:</span></span><br><span class="line">        <span class="keyword">if</span> root == <span class="literal">None</span>:</span><br><span class="line">            <span class="keyword">return</span></span><br><span class="line">        stack = []</span><br><span class="line">        result = []</span><br><span class="line">        node = root</span><br><span class="line">        <span class="keyword">while</span> node <span class="keyword">or</span> stack:</span><br><span class="line">            <span class="keyword">while</span> node:</span><br><span class="line">                <span class="comment"># 从根节点开始，一直找它的左子树</span></span><br><span class="line">                result.append(node.val)</span><br><span class="line">                stack.append(node)</span><br><span class="line">                node = node.left</span><br><span class="line">            <span class="comment"># while结束表示当前节点node为空，即前一个节点没有左子树了</span></span><br><span class="line">            node = stack.pop()</span><br><span class="line">            <span class="comment"># 开始查看它的右子树</span></span><br><span class="line">            node = node.right</span><br><span class="line">        <span class="keyword">return</span> result</span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">inOrder</span><span class="params">(self,root)</span>:</span></span><br><span class="line">    <span class="keyword">if</span> root == <span class="literal">None</span>:</span><br><span class="line">        <span class="keyword">return</span></span><br><span class="line">    stack = []</span><br><span class="line">    result = []</span><br><span class="line">    node = root</span><br><span class="line">    <span class="keyword">while</span> node <span class="keyword">or</span> stack:</span><br><span class="line">        <span class="keyword">while</span> node:</span><br><span class="line">            <span class="comment">#　从根节点开始，一直找到左子树</span></span><br><span class="line">            stack.append(node)</span><br><span class="line">            node = node.left</span><br><span class="line">            <span class="comment"># while结束表示当前节点node为空，即前一个节点没有左子树了</span></span><br><span class="line">        node = stack.pop()</span><br><span class="line">        result.append(node.val)</span><br><span class="line">        node = node.right</span><br><span class="line">    <span class="keyword">return</span> result</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">postOrder</span><span class="params">(self, root)</span>:</span></span><br><span class="line">        <span class="keyword">if</span> root == <span class="literal">None</span>:</span><br><span class="line">            <span class="keyword">return</span></span><br><span class="line">        stack = []</span><br><span class="line">        result = []</span><br><span class="line">        node = root</span><br><span class="line">        <span class="keyword">while</span> node <span class="keyword">or</span> stack:</span><br><span class="line">            <span class="keyword">while</span> node:</span><br><span class="line">                <span class="comment"># 从根节点开始，一直找它的右子树</span></span><br><span class="line">                result.insert(<span class="number">0</span>,node.val)</span><br><span class="line">                stack.append(node)</span><br><span class="line">                node = node.right</span><br><span class="line">            <span class="comment"># while结束表示当前节点node为空，即前一个节点没有右子树了</span></span><br><span class="line">            node = stack.pop()</span><br><span class="line">            <span class="comment"># 开始查看它的左子树</span></span><br><span class="line">            node = node.left</span><br><span class="line">        <span class="keyword">return</span> result</span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">BFS</span><span class="params">(self, root)</span>:</span></span><br><span class="line">		<span class="string">'''广度优先'''</span></span><br><span class="line">	<span class="keyword">if</span> root == <span class="literal">None</span>:</span><br><span class="line">		<span class="keyword">return</span></span><br><span class="line">		<span class="comment"># queue队列，保存节点</span></span><br><span class="line">	queue = []</span><br><span class="line">	vals = []</span><br><span class="line">	queue.append(root)</span><br><span class="line"></span><br><span class="line">	<span class="keyword">while</span> queue:</span><br><span class="line">			<span class="comment"># 拿出队首节点</span></span><br><span class="line">		currentNode = queue.pop(<span class="number">0</span>)</span><br><span class="line">			<span class="comment">#vals.append(currentNode.val)</span></span><br><span class="line">		vals.append(currentNode.val)</span><br><span class="line">		<span class="keyword">if</span> currentNode.left:</span><br><span class="line">			queue.append(currentNode.left)</span><br><span class="line">		<span class="keyword">if</span> currentNode.right:</span><br><span class="line">			queue.append(currentNode.right)</span><br><span class="line">		<span class="keyword">return</span> vals</span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">DFS</span><span class="params">(self, root)</span>:</span></span><br><span class="line">		<span class="string">'''深度优先'''</span></span><br><span class="line">	<span class="keyword">if</span> root == <span class="literal">None</span>:</span><br><span class="line">		<span class="keyword">return</span></span><br><span class="line">		<span class="comment"># 栈用来保存未访问节点</span></span><br><span class="line">	stack = []</span><br><span class="line">		<span class="comment"># vals保存节点值，作为结果</span></span><br><span class="line">	vals = []</span><br><span class="line">	stack.append(root)</span><br><span class="line"></span><br><span class="line">	<span class="keyword">while</span> stack:</span><br><span class="line">		<span class="comment"># 拿出栈顶节点</span></span><br><span class="line">		currentNode = stack.pop()</span><br><span class="line">		vals.append(currentNode.val)</span><br><span class="line">		<span class="comment">#print(currentNode.val, end=' ')</span></span><br><span class="line">		<span class="keyword">if</span> currentNode.right:</span><br><span class="line">			stack.append(currentNode.right)</span><br><span class="line">		<span class="keyword">if</span> currentNode.left:</span><br><span class="line">			stack.append(currentNode.left)			</span><br><span class="line">		<span class="keyword">return</span> vals</span><br></pre></td></tr></table></figure>
<h3 id="二叉堆"><a href="#二叉堆" class="headerlink" title="二叉堆"></a>二叉堆</h3></li>
</ul>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">BinHeap</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span><span class="params">(self)</span>:</span></span><br><span class="line">        self.heapList = [<span class="number">0</span>]</span><br><span class="line">        self.currentSize = <span class="number">0</span></span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">percUp</span><span class="params">(self,i)</span>:</span></span><br><span class="line">        <span class="keyword">while</span> i // <span class="number">2</span> &gt; <span class="number">0</span>:</span><br><span class="line">          <span class="keyword">if</span> self.heapList[i] &lt; self.heapList[i // <span class="number">2</span>]:</span><br><span class="line">             tmp = self.heapList[i // <span class="number">2</span>]</span><br><span class="line">             self.heapList[i // <span class="number">2</span>] = self.heapList[i]</span><br><span class="line">             self.heapList[i] = tmp</span><br><span class="line">          i = i // <span class="number">2</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">insert</span><span class="params">(self,k)</span>:</span></span><br><span class="line">      self.heapList.append(k)</span><br><span class="line">      self.currentSize = self.currentSize + <span class="number">1</span></span><br><span class="line">      self.percUp(self.currentSize)</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">percDown</span><span class="params">(self,i)</span>:</span></span><br><span class="line">      <span class="keyword">while</span> (i * <span class="number">2</span>) &lt;= self.currentSize:</span><br><span class="line">          mc = self.minChild(i)</span><br><span class="line">          <span class="keyword">if</span> self.heapList[i] &gt; self.heapList[mc]:</span><br><span class="line">              tmp = self.heapList[i]</span><br><span class="line">              self.heapList[i] = self.heapList[mc]</span><br><span class="line">              self.heapList[mc] = tmp</span><br><span class="line">          i = mc</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">minChild</span><span class="params">(self,i)</span>:</span></span><br><span class="line">      <span class="keyword">if</span> i * <span class="number">2</span> + <span class="number">1</span> &gt; self.currentSize:</span><br><span class="line">          <span class="keyword">return</span> i * <span class="number">2</span></span><br><span class="line">      <span class="keyword">else</span>:</span><br><span class="line">          <span class="keyword">if</span> self.heapList[i*<span class="number">2</span>] &lt; self.heapList[i*<span class="number">2</span>+<span class="number">1</span>]:</span><br><span class="line">              <span class="keyword">return</span> i * <span class="number">2</span></span><br><span class="line">          <span class="keyword">else</span>:</span><br><span class="line">              <span class="keyword">return</span> i * <span class="number">2</span> + <span class="number">1</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">delMin</span><span class="params">(self)</span>:</span></span><br><span class="line">      retval = self.heapList[<span class="number">1</span>]</span><br><span class="line">      self.heapList[<span class="number">1</span>] = self.heapList[self.currentSize]</span><br><span class="line">      self.currentSize = self.currentSize - <span class="number">1</span></span><br><span class="line">      self.heapList.pop()</span><br><span class="line">      self.percDown(<span class="number">1</span>)</span><br><span class="line">      <span class="keyword">return</span> retval</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">buildHeap</span><span class="params">(self,alist)</span>:</span></span><br><span class="line">      i = len(alist) // <span class="number">2</span></span><br><span class="line">      self.currentSize = len(alist)</span><br><span class="line">      self.heapList = [<span class="number">0</span>] + alist[:]</span><br><span class="line">      <span class="keyword">while</span> (i &gt; <span class="number">0</span>):</span><br><span class="line">          self.percDown(i)</span><br><span class="line">          i = i - <span class="number">1</span></span><br></pre></td></tr></table></figure>


      
    </div>
    <div class="article-footer">
      <blockquote class="mt-2x">
  <ul class="post-copyright list-unstyled">
    
    <li class="post-copyright-link hidden-xs">
      <strong>本文链接：</strong>
      <a href="http://sunjinxu99.gitee.io/blog/2020/03/26/%E6%A0%91/" title="二叉树" target="_blank" rel="external">http://sunjinxu99.gitee.io/blog/2020/03/26/%E6%A0%91/</a>
    </li>
    
    <li class="post-copyright-license">
      <strong>版权声明： </strong> 本博客所有文章除特别声明外，均采用 <a href="http://creativecommons.org/licenses/by/4.0/deed.zh" target="_blank" rel="external">CC BY 4.0 CN协议</a> 许可协议。转载请注明出处！
    </li>
  </ul>
</blockquote>


<div class="panel panel-default panel-badger">
  <div class="panel-body">
    <figure class="media">
      <div class="media-left">
        <a href="" target="_blank" class="img-burn thumb-sm visible-lg">
          <img src="/blog/images/avatar.png" class="img-rounded w-full" alt="">
        </a>
      </div>
      <div class="media-body">
        <h3 class="media-heading"><a href="" target="_blank"><span class="text-dark">小马</span><small class="ml-1x"></small></a></h3>
        <div></div>
      </div>
    </figure>
  </div>
</div>


    </div>
  </article>
  
    
  <section id="comments">
  	
      <div id="vcomments"></div>
    
  </section>


  
</div>

  <nav class="bar bar-footer clearfix" data-stick-bottom>
  <div class="bar-inner">
  
  <ul class="pager pull-left">
    
    <li class="prev">
      <a href="/blog/2020/03/26/%E9%80%92%E5%BD%92/" title="递归"><i class="icon icon-angle-left" aria-hidden="true"></i><span>&nbsp;&nbsp;Newer</span></a>
    </li>
    
    
    <li class="next">
      <a href="/blog/2020/03/26/%E5%93%88%E5%B8%8C%E8%A1%A8/" title="哈希表"><span>Older&nbsp;&nbsp;</span><i class="icon icon-angle-right" aria-hidden="true"></i></a>
    </li>
    
    
  </ul>
  
  
  
  <div class="bar-right">
    
  </div>
  </div>
</nav>
  


</main>

  <footer class="footer" itemscope itemtype="http://schema.org/WPFooter">
	
    <div class="copyright">
    	
        <div class="publishby">
        	Theme by <a href="https://github.com/cofess" target="_blank"> cofess </a>base on <a href="https://github.com/cofess/hexo-theme-pure" target="_blank">pure</a>.
        </div>
    </div>
</footer>
  <script src="//cdn.jsdelivr.net/npm/jquery@1.12.4/dist/jquery.min.js"></script>
<script>
window.jQuery || document.write('<script src="js/jquery.min.js"><\/script>')
</script>

<script src="/blog/js/plugin.min.js"></script>


<script src="/blog/js/application.js"></script>


    <script>
(function (window) {
    var INSIGHT_CONFIG = {
        TRANSLATION: {
            POSTS: 'Posts',
            PAGES: 'Pages',
            CATEGORIES: 'Categories',
            TAGS: 'Tags',
            UNTITLED: '(Untitled)',
        },
        ROOT_URL: '/blog/',
        CONTENT_URL: '/blog/content.json',
    };
    window.INSIGHT_CONFIG = INSIGHT_CONFIG;
})(window);
</script>

<script src="/blog/js/insight.js"></script>






   




   
    
  <script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/valine"></script>
  <script type="text/javascript">
  var GUEST = ['nick', 'mail', 'link'];
  var meta = 'nick,mail,link';
  meta = meta.split(',').filter(function(item) {
    return GUEST.indexOf(item) > -1;
  });
  new Valine({
    el: '#vcomments',
    verify: false,
    notify: false,
    appId: '',
    appKey: '',
    placeholder: 'Just go go',
    avatar: 'mm',
    meta: meta,
    pageSize: '10' || 10,
    visitor: false
  });
  </script>

     







</body>
</html>